#define _CRT_SECURE_NO_WARNINGS 1

#include"tree.h"
#include"Queue.h"

void PrevOrder(Tnode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->a);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
void InOrder(Tnode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->a);
	InOrder(root->right);
}
void EndOrder(Tnode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	EndOrder(root->left);
	EndOrder(root->right);
	printf("%d ", root->a);
}

int TreeSize(Tnode* root)
{
	return root == NULL ? 0 :
	TreeSize(root->left) + TreeSize(root->right) + 1;
}
int LeafSsize(Tnode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return LeafSsize(root->left) + LeafSsize(root->right);
}
int LevelSize(Tnode* root, int k)
{
	if (root==NULL)
		return 0;

	if (k == 1)
		return 1;

	return LevelSize(root->left, k - 1)
		+ LevelSize(root->right, k - 1);
}

int TreeHeight(Tnode* root)
{
	if (root == NULL)
		return 0;

	int heightleft = TreeHeight(root->left);
	int heightright = TreeHeight(root->right);

	return heightleft > heightright ? heightleft + 1 : heightright + 1;
}
void TreeDestroy(Tnode* root)
{
	if (root == NULL)
		return;

	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}

Tnode* CreatTree(char* ch, int* pi)
{
	if (ch[(*pi)++] == '#')
	{
		return NULL;
	}

	Tnode* root = (Tnode*)malloc(sizeof(Tnode));
	assert(root);

	root->a = ch[(*pi)++];
	root->left = CreatTree(ch, pi);
	root->right = CreatTree(ch, pi);

	return root;
}
Tnode* findNode(Tnode* root, TreeTypedate x)
{
	if (root == NULL)
		return NULL;

	if (root->a == x)
		return root;

	Tnode* ret1 = findNode(root->left, x);
	if (ret1)
		return ret1;

	Tnode* ret2 = findNode(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

bool isValTree(Tnode* root)
{
	if (root == NULL)
		return true;

	if (root->left && root->left->a != root->a)
		return false;

	if (root->right && root->right->a != root->a)
		return false;

	return isValTree(root->left) && isValTree(root->right);
}
bool issameTree(Tnode* p, Tnode* q)
{
	if (p == NULL && q == NULL)
		return true;

	if (p == NULL || q == NULL)
		return false;

	if (p->a != q->a)
		return false;

	return issameTree(p->left, q->left) && issameTree(p->right, q->right);

}
bool _mirrorTree(Tnode* root1, Tnode* root2)
{
	if (root1 == NULL && root2 == NULL)
		return true;

	if (root1 == NULL || root2 == NULL)
		return false;

	if (root1->a != root2->a)
		return false;

	return _mirrorTree(root1->left, root2->right) && _mirrorTree(root1->right, root2->left);
}
bool mirrorTree(Tnode* root)
{
	if (root == NULL)
		return true;

	return _mirrorTree(root->left, root->right);
}
bool issunTree(Tnode* root, Tnode* subroot)
{
	if (root == NULL)
		return false;

	return issameTree(root, subroot)
		|| issunTree(root->left, subroot)
		|| issunTree(root->right, subroot);
}

void levelOrder(Tnode* root)
{
	queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	else
		return;

	while (!QueueEmpty(&q))
	{
		Tnode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->a);

		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");

	QueueDestroy(&q);
}

void levelOrdermax(Tnode* root)
{
	queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);
	else
		return;

	int size = 1;
	while (!QueueEmpty(&q))
	{
		while (size--)
		{
			Tnode* front = QueueFront(&q);
			QueuePop(&q);

			printf("%d ", front->a);

			if (front->left)
				QueuePush(&q, front->left);

			if (front->right)
				QueuePush(&q, front->right);
		}
		printf("\n");
		size = QueueSize(&q);
	}
	printf("\n");

	QueueDestroy(&q);
}

bool completeTree(Tnode* root)
{
	queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		Tnode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	while (!QueueEmpty(&q))
	{
		Tnode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}